package interview.i_002_dataStructure;

import sun.misc.Unsafe;

import java.util.Arrays;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * https://www.bilibili.com/video/BV17i4y1x71z
 */
public class T002_ConcurrentHashMap<K, V> {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Object> map = new ConcurrentHashMap<>();
        for (int i = 0; i < 11; i++) {
            map.put(String.valueOf(i), i);
        }
        new Thread(() -> map.put("哈哈", "哈哈"), "哈哈").start();
        new Thread(() -> map.put("呵呵", "呵呵"), "呵呵").start();
        new Thread(() -> map.put("嘻嘻", "嘻嘻"), "嘻嘻").start();
    }

    private static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
    private static final int DEFAULT_CAPACITY = 16;
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    private static final float LOAD_FACTOR = 0.75f; // 加载因子
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    private static final int MIN_TRANSFER_STRIDE = 16;
    private static final int RESIZE_STAMP_BITS = 16;
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    static final int MOVED = -1;
    static final int TREEBIN = -2;
    static final int RESERVED = -3;
    static final int HASH_BITS = 0x7fffffff;
    static final int NCPU = Runtime.getRuntime().availableProcessors(); // CPU 核数
    transient volatile Node<K, V>[] table; // 存放元素
    private transient volatile Node<K, V>[] nextTable; // 扩容
    private transient volatile long baseCount; // 实际容量，还需加上 counterCells
    /**
     * sizeCtl 为 0，代表数组未初始化，且数组的初始容量为 16
     * sizeCtl 为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值(初始容量 * 0.75)
     * sizeCtl 为 -1，表示数组正在进行初始化
     * sizeCtl 小于 0，并且不是 -1，表示数组正在扩容，-(1+n)，表示此时有n个线程正在共同完成数组的扩容操作
     */
    private transient volatile int sizeCtl;
    private transient volatile int transferIndex; // 协助扩容
    private transient volatile int cellsBusy; // counterCells 状态
    private transient volatile CounterCell[] counterCells; // 实际容量

    public T002_ConcurrentHashMap() {
    }

    public T002_ConcurrentHashMap(int initialCapacity) {
        this(initialCapacity, LOAD_FACTOR, 1);
    }

    public T002_ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }

    public T002_ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) {
            throw new IllegalArgumentException();
        }
        if (initialCapacity < concurrencyLevel) {
            initialCapacity = concurrencyLevel;
        }
        long size = (long) (1.0 + (long) initialCapacity / loadFactor);
        int cap = (size >= (long) MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int) size);
        this.sizeCtl = cap;
    }

    public T002_ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        tryPresize(m.size());
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            putVal(e.getKey(), e.getValue(), false);
        }
    }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) { // 不允许
            throw new NullPointerException();
        }
        int hash = spread(key.hashCode()); // 获取 hash，一定是正数
        int binCount = 0;
        for (Node<K, V>[] tab = table; ; ) {
            Node<K, V> f;
            int n, i, fh;
            K fk;
            V fv;
            if (tab == null || (n = tab.length) == 0) {
                tab = initTable(); // 初始化
            } else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 当前桶中元素为空
                if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value))) { // CAS 方式添加元素
                    break; // 添加成功
                }
            } else if ((fh = f.hash) == MOVED) { // 当前桶有元素，若是 MOVED，表示数组正在扩容
                tab = helpTransfer(tab, f); // 协助扩容
            } else if (onlyIfAbsent && fh == hash
                    && ((fk = f.key) == key || (fk != null && key.equals(fk))) // 在不获取锁的情况下检查第一个节点
                    && (fv = f.val) != null) {
                return fv;
            } else {
                V oldVal = null;
                synchronized (f) { // 锁住当前桶中元素
                    if (tabAt(tab, i) == f) { // 判断桶中的当前位置节点是否改变(存在其它线程做完操作后变成树)
                        if (fh >= 0) { // hash >= 0 表示为链表结构
                            binCount = 1;
                            for (Node<K, V> e = f; ; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                        ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent) {
                                        e.val = value;
                                    }
                                    break;
                                }
                                Node<K, V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K, V>(hash, key, value);
                                    break;
                                }
                            }
                        } else if (f instanceof TreeBin) { // hash < 0 可能为树结构
                            Node<K, V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent) {
                                    p.val = value;
                                }
                            }
                        } else if (f instanceof ReservationNode) {
                            throw new IllegalStateException("Recursive update");
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD) { // 链表是否需要转换为红黑树
                        treeifyBin(tab, i);
                    }
                    if (oldVal != null) {
                        return oldVal;
                    }
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

    private final Node<K, V>[] initTable() { // 可以多线程执行：自旋 + CAS
        Node<K, V>[] tab;
        int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0) {
                Thread.yield(); // 有其它线程在做初始化
            } else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) { // 双端检测
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 数组长度
                        @SuppressWarnings("unchecked")
                        Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2); // n - n/4 = 0.75 * n
                    }
                } finally {
                    sizeCtl = sc; // 初始化后 sizeCtl 记录的是扩容阈值
                }
                break;
            }
        }
        return tab;
    }

    private final void addCount(long x, int check) { // 维护集合长度，判断是否需要扩容
        CounterCell[] cs;
        long b, s;
        if ((cs = counterCells) != null ||
                !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // 尝试直接修改 baseCount 大小
            CounterCell c;
            long v;
            int m;
            boolean uncontended = true;
            if (cs == null || (m = cs.length - 1) < 0 ||
                    (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
                    !(uncontended = U.compareAndSwapLong(c, CELLVALUE, v = c.value, v + x))) { // 尝试直接修改 counterCells 数组
                fullAddCount(x, uncontended); // 直接修改 baseCount 大小失败，修改 CounterCell 数组
                return;
            }
            if (check <= 1) { // 只有一个元素不需要检查扩容
                return;
            }
            s = sumCount(); // 获取实际容量，用于判断 Map 是否需要扩容
        }
        if (check >= 0) {
            Node<K, V>[] tab, nt;
            int n, sc;
            while (s >= (long) (sc = sizeCtl) && // 达到扩容阈值
                    (tab = table) != null && // 数组不为 null
                    (n = tab.length) < MAXIMUM_CAPACITY) { // 数组长度没有达到最大
                int rs = resizeStamp(n); // 为了下面把 sizeCtl 改为负数，表示数组正在扩容
                if (sc < 0) { // 有别的线程正在扩容
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || // 扩容操作是否完成
                            sc == rs + MAX_RESIZERS || (nt = nextTable) == null || // 协助扩容线程是否达到最大
                            transferIndex <= 0) {
                        break;
                    }
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { // 扩容的线程数量 +1
                        transfer(tab, nt); // 协助扩容，nt 不可能为 null，nt 为新的数组
                    }
                } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) {
                    transfer(tab, null); // 扩容
                }
                s = sumCount();
            }
        }
    }

    final long sumCount() { // 获取 Map 中元素数量
        CounterCell[] cs = counterCells;
        long sum = baseCount;
        if (cs != null) {
            for (CounterCell c : cs) {
                if (c != null) {
                    sum += c.value;
                }
            }
        }
        return sum;
    }

    private final void fullAddCount(long x, boolean wasUncontended) {
        int h;

        if ((h = ThreadLocalRandom.getProbe()) == 0) {
            ThreadLocalRandom.localInit();
            h = ThreadLocalRandom.getProbe();
            wasUncontended = true;
        }

        boolean collide = false; // 碰撞
        for (; ; ) { // 自旋
            CounterCell[] cs;
            CounterCell c;
            int n;
            long v;
            if ((cs = counterCells) != null && (n = cs.length) > 0) { // counterCells 数组不为 null
                if ((c = cs[(n - 1) & h]) == null) { // 数组中对应元素为 null，没有发生碰撞，直接添加元素，元素初始值为 1
                    if (cellsBusy == 0) {
                        CounterCell r = new CounterCell(x);
                        if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                            boolean created = false;
                            try {
                                CounterCell[] rs;
                                int m, j;
                                if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) {
                                    rs[j] = r; // 赋值
                                    created = true;
                                }
                            } finally {
                                cellsBusy = 0; // 恢复状态，就算异常
                            }
                            if (created) {
                                break;
                            }
                            continue;
                        }
                    }
                    collide = false;
                } else if (!wasUncontended) {
                    wasUncontended = true;
                } else if (U.compareAndSwapLong(c, CELLVALUE, v = c.value, v + x)) { // 数组中对应元素不为 null，尝试直接修改元素的值
                    break;
                } else if (counterCells != cs || n >= NCPU) { // 数组长度 >= CPU 核数，不再扩容
                    collide = false;
                } else if (!collide) {
                    collide = true;
                } else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                    try {
                        if (counterCells == cs) { // 多次自旋还没修改成功(容易 hash 碰撞)，对 counterCells 数组扩容
                            counterCells = Arrays.copyOf(cs, n << 1);
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;
                }
                h = ThreadLocalRandom.advanceProbe(h); // 每次自旋重新获取随机值，用于计算下标
            } else if (cellsBusy == 0 && counterCells == cs && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { // 为 null
                boolean init = false;
                try {
                    if (counterCells == cs) { // 对 counterCells 数组做初始化
                        CounterCell[] rs = new CounterCell[2];
                        rs[h & 1] = new CounterCell(x); // 将 1 放入
                        counterCells = rs;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0; // 恢复状态，就算异常
                }
                if (init) {
                    break;
                }
            } else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x)) { // 尝试直接修改
                break;
            }
        }
    }

    final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
        Node<K, V>[] nextTab;
        int sc;
        if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K, V>) f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) {
                    break;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }

    private final void treeifyBin(Node<K, V>[] tab, int index) {
        Node<K, V> b;
        int n;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) { // 还需要满足才转换
                tryPresize(n << 1); // 扩容
            } else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 转红黑树
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        TreeNode<K, V> hd = null, tl = null;
                        for (Node<K, V> e = b; e != null; e = e.next) {
                            TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null);
                            if ((p.prev = tl) == null) {
                                hd = p;
                            } else {
                                tl.next = p;
                            }
                            tl = p;
                        }
                        setTabAt(tab, index, new TreeBin<K, V>(hd));
                    }
                }
            }
        }
    }

    private final void tryPresize(int size) { // 尝试扩容
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); // 原来的两倍
        int sc;
        while ((sc = sizeCtl) >= 0) {
            Node<K, V>[] tab = table;
            int n;
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                }
            } else if (c <= sc || n >= MAXIMUM_CAPACITY) {
                break;
            } else if (tab == table) {
                int rs = resizeStamp(n);
                if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) {
                    transfer(tab, null); // 扩容
                }
            }
        }
    }

    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

    private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) { // 扩容数组
        int n = tab.length, stride;
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) {
            stride = MIN_TRANSFER_STRIDE; // 多核 CPU，把数组分为几份，多个线程一起做扩容这件事，每个线程最少负责 16 个元素
        }

        if (nextTab == null) {
            try {
                @SuppressWarnings("unchecked")
                Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1]; // 新建数组，容量翻倍
                nextTab = nt;
            } catch (Throwable ex) {
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab; // 赋值，协助扩容需要用
            transferIndex = n; // 旧数组大小
        }
        int nextn = nextTab.length;
        ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab); // 用于标识已被迁移，hash 值为 MOVE
        boolean advance = true;
        boolean finishing = false;
        for (int i = 0, bound = 0; ; ) {
            Node<K, V> f;
            int fh;
            while (advance) { // 为线程分配任务，下标从哪到哪，从后往前迁移
                int nextIndex, nextBound;
                if (--i >= bound || finishing) {
                    advance = false;
                } else if ((nextIndex = transferIndex) <= 0) { // nextIndex 赋值为旧数组长度
                    i = -1;
                    advance = false;
                } else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
                        nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) { // 扩容完成
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1); // 阈值 (2n - n/2) = 1.5 * n = 0.75 * 2n
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { // 扩容线程 -1
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
                        return; // 没有扩容完，继续领任务扩容
                    }
                    finishing = advance = true;
                    i = n;
                }
            } else if ((f = tabAt(tab, i)) == null) { // 判断原素组中的元素是否为 null
                advance = casTabAt(tab, i, null, fwd); // 往元素组放入标记
            } else if ((fh = f.hash) == MOVED) { // 不是 null，且已经迁移过了
                advance = true;
            } else {
                synchronized (f) { // 开始做迁移，其它线程无法添加元素，锁的为桶中头部节点元素
                    if (tabAt(tab, i) == f) {
                        Node<K, V> ln, hn;
                        if (fh >= 0) {
                            int runBit = fh & n;
                            Node<K, V> lastRun = f;
                            for (Node<K, V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            } else {
                                hn = lastRun;
                                ln = null;
                            }
                            for (Node<K, V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash;
                                K pk = p.key;
                                V pv = p.val;
                                if ((ph & n) == 0) {
                                    ln = new Node<K, V>(ph, pk, pv, ln);
                                } else {
                                    hn = new Node<K, V>(ph, pk, pv, hn);
                                }
                            }
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        } else if (f instanceof TreeBin) {
                            TreeBin<K, V> t = (TreeBin<K, V>) f;
                            TreeNode<K, V> lo = null, loTail = null;
                            TreeNode<K, V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K, V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K, V> p = new TreeNode<K, V>(h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null) {
                                        lo = p;
                                    } else {
                                        loTail.next = p;
                                    }
                                    loTail = p;
                                    ++lc;
                                } else {
                                    if ((p.prev = hiTail) == null) {
                                        hi = p;
                                    } else {
                                        hiTail.next = p;
                                    }
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K, V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K, V>(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd); // 迁移完成后放入标记
                            advance = true;
                        }
                    }
                }
            }
        }
    }

    static <K, V> Node<K, V> untreeify(Node<K, V> b) {
        Node<K, V> hd = null, tl = null;
        for (Node<K, V> q = b; q != null; q = q.next) {
            Node<K, V> p = new Node<K, V>(q.hash, q.key, q.val);
            if (tl == null) {
                hd = p;
            } else {
                tl.next = p;
            }
            tl = p;
        }
        return hd;
    }

    private static final int tableSizeFor(int c) {
        int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

    @jdk.internal.vm.annotation.Contended
    static final class CounterCell {
        volatile long value;

        CounterCell(long x) {
            value = x;
        }
    }

    static class Node<K, V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K, V> next;

        Node(int hash, K key, V val) {
            this.hash = hash;
            this.key = key;
            this.val = val;
        }

        Node(int hash, K key, V val, Node<K, V> next) {
            this(hash, key, val);
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return val;
        }

        public final int hashCode() {
            return key.hashCode() ^ val.hashCode();
        }

        public final String toString() {
            return Helpers.mapEntryToString(key, val);
        }

        public final V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        public final boolean equals(Object o) {
            Object k, v, u;
            Node<?, ?> e;
            return ((o instanceof Node) &&
                    (k = (e = (Node<?, ?>) o).getKey()) != null &&
                    (v = e.getValue()) != null &&
                    (k == key || k.equals(key)) &&
                    (v == (u = val) || v.equals(u)));
        }

        Node<K, V> find(int h, Object k) {
            Node<K, V> e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

    static final class TreeBin<K, V> extends Node<K, V> {
        TreeNode<K, V> root;
        volatile TreeNode<K, V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1;
        static final int WAITER = 2;
        static final int READER = 4;

        TreeBin(TreeNode<K, V> b) {
            super(TREEBIN, null, null);
        }

        final Node<K, V> find(int h, Object k) {
            return null;
        }

        final TreeNode<K, V> putTreeVal(int h, K k, V v) {
            return null;
        }
    }

    static final class TreeNode<K, V> extends Node<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        TreeNode<K, V> prev;
        boolean red;

        TreeNode(int hash, K key, V val, Node<K, V> next, TreeNode<K, V> parent) {
            super(hash, key, val, next);
            this.parent = parent;
        }

        Node<K, V> find(int h, Object k) {
            return findTreeNode(h, k, null);
        }

        final TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
            return null;
        }
    }

    static final class ForwardingNode<K, V> extends Node<K, V> {
        final Node<K, V>[] nextTable;

        ForwardingNode(Node<K, V>[] tab) {
            super(MOVED, null, null);
            this.nextTable = tab;
        }

        Node<K, V> find(int h, Object k) {
            return null;
        }
    }

    static final class ReservationNode<K, V> extends Node<K, V> {
        ReservationNode() {
            super(RESERVED, null, null);
        }

        Node<K, V> find(int h, Object k) {
            return null;
        }
    }

    // 避免报错
    private static Unsafe U;
    private static long SIZECTL;
    private static long TRANSFERINDEX;
    private static long BASECOUNT;
    private static long CELLSBUSY;
    private static long CELLVALUE;
    private static int ABASE;
    private static int ASHIFT;

    {
        try {
            U = sun.misc.Unsafe.getUnsafe();
            Class<?> k = T002_ConcurrentHashMap.class;
            SIZECTL = U.objectFieldOffset(k.getDeclaredField("sizeCtl"));
            TRANSFERINDEX = U.objectFieldOffset(k.getDeclaredField("transferIndex"));
            BASECOUNT = U.objectFieldOffset(k.getDeclaredField("baseCount"));
            CELLSBUSY = U.objectFieldOffset(k.getDeclaredField("cellsBusy"));
            Class<?> ck = T002_ConcurrentHashMap.CounterCell.class;
            CELLVALUE = U.objectFieldOffset(ck.getDeclaredField("value"));
            Class<?> ak = T002_ConcurrentHashMap.Node[].class;
            ABASE = U.arrayBaseOffset(ak);
            int scale = U.arrayIndexScale(ak);
            if ((scale & (scale - 1)) != 0) {
                throw new Error("data type scale not a power of two");
            }
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Exception e) {
            throw new Error(e);
        }
    }

    static final <K, V> Node<K, V> tabAt(Node<K, V>[] tab, int i) {
        return (Node<K, V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);
    }

    static final <K, V> boolean casTabAt(Node<K, V>[] tab, int i, Node<K, V> c, Node<K, V> v) {
        return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
    }

    static final <K, V> void setTabAt(Node<K, V>[] tab, int i, Node<K, V> v) {
        U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v);
    }

    static class Helpers {
        static String mapEntryToString(Object key, Object val) {
            final String k, v;
            final int klen, vlen;
            final char[] chars = new char[(klen = (k = objectToString(key)).length()) + (vlen = (v = objectToString(val)).length()) + 1];
            k.getChars(0, klen, chars, 0);
            chars[klen] = '=';
            v.getChars(0, vlen, chars, klen + 1);
            return new String(chars);
        }

        private static String objectToString(Object x) {
            String s;
            return (x == null || (s = x.toString()) == null) ? "null" : s;
        }
    }

    static class ThreadLocalRandom {
        private static final int PROBE_INCREMENT = 0x9e3779b9;
        private static final long SEEDER_INCREMENT = 0xbb67ae8584caa73bL;
        private static final AtomicInteger probeGenerator = new AtomicInteger();
        private static final AtomicLong seeder = new AtomicLong(mix64(System.currentTimeMillis()) ^ mix64(System.nanoTime()));
        private static final Unsafe U = sun.misc.Unsafe.getUnsafe();
        private static final long SEED;
        private static final long PROBE;

        static {
            try {
                PROBE = U.objectFieldOffset(Thread.class.getDeclaredField("threadLocalRandomProbe"));
                SEED = U.objectFieldOffset(Thread.class.getDeclaredField("threadLocalRandomSeed"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }

        static final int getProbe() {
            return U.getInt(Thread.currentThread(), PROBE);
        }

        static final int advanceProbe(int probe) {
            probe ^= probe << 13;
            probe ^= probe >>> 17;
            probe ^= probe << 5;
            U.putInt(Thread.currentThread(), PROBE, probe);
            return probe;
        }

        static final void localInit() {
            int p = probeGenerator.addAndGet(PROBE_INCREMENT);
            int probe = (p == 0) ? 1 : p;
            long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
            Thread t = Thread.currentThread();
            U.putLong(t, SEED, seed);
            U.putInt(t, PROBE, probe);
        }

        private static long mix64(long z) {
            z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
            z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
            return z ^ (z >>> 33);
        }
    }
}
